import random
import testutils
import bestsubarray

class Submatrix:
    def __init__(self, mat):
        self.mat = mat
        self.start_row = 0 # inclusive
        self.start_col = 0
        self.end_row = 0 # exclusive
        self.end_col = 0
        self.val = 0

    def get_copy(self):
        return [row[self.start_col : self.end_col] for row in self.mat[self.start_row : self.end_row]]

    def __str__(self):
        return testutils.matrix_to_string(self.get_copy())

    def __repr__(self):
        return repr(self.get_copy())

def highest_value_submatrix_brute_force(mat):
    """Given a matrix of integers, finds the submatrix with the largest
    sum of element values. This brute force algorithm simply calculates the 
    sum value of every possible submatrix and takes the largest one. The
    running time is O(N^3 * M^3), where N and M are the dimensions of the 
    matrix.
    """
    numrows = len(mat)
    if numrows == 0:
        return [[]]
    numcols = len(mat[0])
    if numcols == 0:
        return [[]]

    best = Submatrix(mat)

    for start_row in range(numrows):
        for start_col in range(numcols):
            for end_row in range(start_row, numrows):
                for end_col in range(start_col, numcols):
                    val = _sum_matrix(mat, start_row, end_row, start_col, end_col)
                    if val >  best.val:
                        best.val = val
                        best.start_row = start_row
                        best.end_row = end_row + 1
                        best.start_col = start_col
                        best.end_col = end_col + 1

    return best

def highest_value_submatrix(mat):
    """Given a matrix of integers, finds the submatrix with the largest
    sum of element values. This optimized algorithm has complexity
    O(min(M,N)^2 * max(M,N)), where M and N are the dimensions of the matrix.
    """
    is_transverse = False
    numrows = len(mat)
    if numrows == 0:
        return [[]]
    numcols = len(mat[0])
    if numcols == 0:
        return [[]]

    is_transverse = False
    if numrows > numcols:
        # Since the algorithm is O(numrows^2 * numcols), we want to make sure
        # numrows < numcols. 
        is_transverse = True
        mat = list(zip(*mat))
        numrows, numcols = numcols, numrows
    
    best = Submatrix(mat)
    for start_row in range(numrows):
        colsums = [0 for _ in range(numcols)]
        for end_row in range(start_row, numrows):
            for i in range(numcols):
                colsums[i] += mat[end_row][i]
            best_arr = bestsubarray.highest_value_subarray(colsums)
            if best_arr.val > best.val:
                best.val = best_arr.val
                best.start_row = start_row
                best.end_row = end_row + 1
                best.start_col = best_arr.start
                best.end_col = best_arr.end
            
    if is_transverse:
        mat = list(zip(*mat))
        transverse_best = best
        best = Submatrix(mat)
        best.val = transverse_best.val
        best.start_row = transverse_best.start_col
        best.end_row = transverse_best.end_col
        best.start_col = transverse_best.start_row
        best.end_col = transverse_best.end_row

    return best
    
def _sum_matrix(mat, i_bl, i_tr, j_bl, j_tr):
    if len(mat) == 0:
        return 0
    return sum((sum(row[j_bl : j_tr + 1]) for row in mat[i_bl : i_tr + 1]))


if __name__ == "__main__":

    numrows = 10
    numcols = 12
    domain = list(range(-1000,1000))
    mat = []
    for _ in range(numrows):
        mat.append(random.sample(domain, numcols))
    
    testutils.print_matrix(mat)

    # compute the highest value submatrix using both algorithms. The
    # results should be identical.
    print()
    print(highest_value_submatrix_brute_force(mat))
    print()
    print(highest_value_submatrix(mat))